package leetcode_100;


/**
 *@author 周杨
 *NQueensII_52 N皇后问题 构造n*n棋盘  保证每个皇后不在同一直线、斜线上  
 *describe: 回溯法解决 AC 33%
 *2018年5月6日 下午3:36:32
 */
public class NQueensII_52 {
	boolean board[][];
	int res=0;
	int n;
	public static void main(String[] args) {
		NQueensII_52 test=new NQueensII_52();
		System.out.println(test.solveNQueens(4));

	}
	
	public int solveNQueens(int n) {
		this.board=new boolean [n][n];
		this.n=n;
		help(0);
        return this.res;
    }
	
	public void help(int count) {
		if(count==this.n) {
			++this.res;
			return;
		}
		for(int i=0;i<this.n;++i) {
			if(judge(count,i)) {//可以放
				board[count][i]=true;
				help(count+1);
				board[count][i]=false;
			}
		}
	}
	
	public void print() {
		for(int i=0;i<this.n;++i) {
			for(int j=0;j<this.n;++j) {
			System.out.print(board[i][j]+" ");	
			}
			System.out.println();
		}
	}
	
	public boolean judge(int x,int y) {
		for(int i=0;i<n;++i) {//检查横向纵向
			if(board[i][y])
				return false;
			if(board[x][i])
				return false;
		}
		int count=1;
		while(x+count<n&&y+count<n) {
			if(board[x+count][y+count])
				return false;
			++count;
		}
		count=1;
		while(x-count>=0&&y-count>=0) {
			if(board[x-count][y-count])
				return false;
			++count;
		}
		count=1;
		while(x+count<n&&y-count>=0) {
			if(board[x+count][y-count])
				return false;
			++count;
		}
		count=1;
		while(y+count<n&&x-count>=0) {
			if(board[x-count][y+count])
				return false;
			++count;
		}
		return true;
		
	}

}
